package com.cat.dataStructure;
/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/maximum-sum-of-two-non-overlapping-subarrays/
 * @create 2025/8/15 15:40
 * @since JDK17
 */

public class Solution16 {
    public int f(int[] prefix, int f, int s) {
        int ans = 0, max = 0, n = prefix.length;
        for (int i = f + s; i < n; i++) {
            max = Math.max(max, prefix[i - s] - prefix[i - s - f]);
            ans = Math.max(ans, max + prefix[i] - prefix[i - s]);
        }
        return ans;
    }


    public int maxSumTwoNoOverlap(int[] nums, int f, int s) {
        int n = nums.length, max;
        int[] prefix = new int[n + 1];
        for (int i = 0; i < n; i++) {   // 计算出前缀和数组
            prefix[i + 1] = nums[i] + prefix[i];
        }
        //
        return Math.max(f(prefix, f, s), f(prefix, s, f));
    }
}
